use data_structure::prelude::*;

fn next_val(reg: &str) -> Table<DNode<i64>> {
    let reg = reg.as_bytes();
    let mut tab: Table<DNode<i64>> = Table::new();
    let len = reg.len();
    tab.push(-1i64);
    if len > 1 {
        tab.push(0i64);
        let (mut i, mut j) = (1, 0);
        while i < len {
            match (reg[i] == reg[j], j) {
                (true, _) => {
                    j += 1;
                    i += 1;
                    tab.push(j as i64);
                }
                (false, 0) => {
                    i += 1;
                    tab.push(0i64);
                }
                _ => j = tab.at(j as u64).unwrap() as usize,
            }
        }
    }
    tab
}

fn str_kmp(string: &str, reg: &str) -> i64 {
    let (str_len, reg_len) = (string.len(), reg.len());
    assert!(str_len >= reg_len);
    let next = next_val(reg);
    let (string, reg) = (string.as_bytes(), reg.as_bytes());
    let (mut i, mut j) = (0, 0);
    while i < str_len && j < reg_len {
        match (string[i] == reg[j], j) {
            (true, _) => {
                i += 1;
                j += 1;
            }
            (false, 0) => i += 1,
            _ => j = next.at(j as u64).unwrap() as usize,
        }
    }
    if j == reg_len {
        (i - j) as i64
    } else {
        -1
    }
}

#[test]
fn kmp() {
    let reg = "abababca";
    let string = "abcabababaabababca";
    assert_eq!(str_kmp(string, reg), 10);
}
